﻿#define _CRT_SECURE_NO_WARNINGS 1
//  二进制加法
/*
string addBinary(string a, string b) 
{
    // 从后往前加
    int enda=static_cast<int>(a.size()-1);
    int endb=static_cast<int>(b.size()-1);

    int va=0;
    int vb=0;
    int x=0; // 进位数

    std::string ans;

    while(enda>=0 || endb>=0)
    {
        if(enda>=0)
            va=a[enda--]-'0';
        if(endb>=0)
            vb=b[endb--]-'0';

        int sum=va+vb+x;

        ans.push_back(sum%2+'0');
        x=sum/2;
        va=vb=0;
    }

    if(x>0)
        ans.push_back('1');

    // 逆置
    std::reverse(ans.begin(),ans.end());

    return ans;
}
*/

// 前 n 个数字二进制中 1 的个数
/*
int BinaryOneCount(int num)
    {
        int count=0;
        for(int i=0;i<32;++i)
        {
            if((num>>i)&1==1)
            {
                ++count;
            }
        }
        return count;
    }

    vector<int> countBits(int n)
    {
        std::vector<int> ans;

        for(int i=0;i<=n;++i)
        {
            ans.push_back(BinaryOneCount(i));
        }

        return ans;
    }
*/

// N 字形变换
/*
string convert(string s, int numRows)
{
    if(numRows<=1) // 如果numRows为1,则直接返回
        return s;
    // 记录每行对应的字符
    std::vector<std::string> vStr(numRows,std::string());
    int i=0; // 当前行
    int flag=-1; // 标识是往上走还是往下走
    for(auto &ch:s)
    {
        vStr[i].push_back(ch);
        if(i==0 || i==numRows-1) // 走到顶或者底则进行反向
        {
            flag=-flag;
        }
        i+=flag;
    }

    std::string ans;
    for(auto &e:vStr) // 将每行相加
    {
        ans+=e;
    }

    return ans;
}
*/

// 盛最多水的容器
/*
int maxArea(vector<int>& height) 
{
    // 双指针
    int left=0;
    int right=static_cast<int>(height.size()-1);
    int ans=0;

    while(left<right)
    {
        // 面积公式: S(i,j)= min(h[i],h[j]) × (j−i)
        // int s=std::min(height[left],height[right])*(right-left);
        int s=(height[left]>height[right]?height[right]:height[left])*(right-left);
        if(s>ans)
        {
            ans=s;
        }
        // 让边小的往内部靠
        if(height[left]>height[right])
        {
            right--;
        }
        else
        {
            left++;
        }
    }

    return ans;
}
*/

// T9键盘---有待优化
/*
class Solution
{
private:
    const char* hashStr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    std::vector<std::string> vStr;

public:

    void dfs(string num, vector<string>& words,string str)
    {
        if(num.empty())
        {
            auto pos=std::find(words.begin(),words.end(),str);
            if(pos!=words.end())
            {
                vStr.push_back(str);
            }
            return;
        }
        int val=num.front()-'0';

        for(int i=0;i<strlen(hashStr[val]);++i)
        {
            dfs(num.substr(1),words,str+hashStr[val][i]);
        }
    }

    vector<string> getValidT9Words(string num, vector<string>& words)
    {
        vStr.clear();

        dfs(num,words,"");

        return vStr;
    }
};
*/
